/*
Scramble String Total Accepted: 32601 Total Submissions: 132882 My Submissions Question Solution
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

great
/    \
gr    eat
/ \    /  \
g   r  e   at
/ \
a   t
To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

rgeat
/    \
rg    eat
/ \    /  \
r   g  e   at
/ \
a   t
We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

rgtae
/    \
rg    tae
/ \    /  \
r   g  ta  e
/ \
t   a
We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.


*/
#include <iostream>
#include "print.h"
#include <vector>
#include <map>
#include <stack>
#include <algorithm>

using namespace std;



class A
{
public:
	A()
	{
		cout << "A called" << endl;
		func();
	}
	~A()
	{
		cout << "A cancel" << endl;
		func();
	}
	virtual void func()
	{
		cout << "A func" << endl;
	}

};




class B : public  A
{
public:
	B()
	{
		cout << "B called" << endl;
		func();
	}
	~B()
	{
		cout << "B cancel" << endl;
		func();
	}
	virtual void func()
	{
		cout << "B func" << endl;
	}
};


void adjustDown(int a[], int k, int len)
{
	int temp = a[k];
	for (int i = 2 * k; i <= len; i *= 2)
	{
		if (i < len && a[i] <a[i + 1])
		{
			i++;
		}
		if (temp >= a[i])
		{
			break;
		}
		else
		{
			a[k] = a[i];
			k = i;
		}

	}
	a[k] = temp;
}


void buildMaxheap(int a[],int len)
{
	for (int i = len/2; i >0; i--)
	{
		adjustDown(a,i,len);
	}
}



int main()
{

	int a[] = {0,20, 18, 22, 16, 30, 19 };
	buildMaxheap(a,6);

	for (int i = 0; i < 7; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;

	system("pause");
	return 0;
}
